//
// Created by Administrator on 2024/9/2.
// 讲解: https://blog.csdn.net/justidle/article/details/104203958
//
#include <iostream>
#include "arrUtil.h"

using namespace std;

void merge(vector<int> &v, int l, int r, int m)
{
    vector<int> t=v;
    int i = l, j = m + 1;
    while (i <= m && j <= r)
    {
        if (t[i] <= t[j])
        {
            //数组v 是从l开始改变的
            v[l] = t[i];
            ++i;
        } else
        {
            v[l] = t[j];
            ++j;
        }
        ++l;
    }
    while (i <= m)
    {
        v[l] = t[i];
        ++i;
        ++l;
    }
    while (j <= r)
    {
        v[l] = t[j];
        ++j;
        ++l;
    }
}

void mergeSort(vector<int> &v, int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        // 因为mergeSort是排序函数
        // 所以执行完这一行, 左边数组就有序了
        mergeSort(v, l, m);
        // 执行完这一行, 右边数组就有序了
        mergeSort(v, m + 1, r);
        // 左边右边都有序了 merge一下就都有序了
        merge(v, l, r, m);
    }
}

int main()
{
    vector<int> v{1, 3, 5, 7, 8, 3, 4, 6, 9};
//    merge(v, 0, v.size() - 1, 1);
//    printVector(v);
    randVector(v,1000);
//    printVector(v);
    mergeSort(v,0,v.size()-1);
//    printVector(v);
    cout<<checkSortVector(v);
    return 0;
}